package com.gxc.tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * 有一棵二叉树，每个节点由一个大写字母标识(最多26个节点）。
 *
 * 现有两组字母，分别表示后序遍历（左孩子->右孩子->父节点）和中序遍历（左孩子->父节点->右孩子）的结果，请你输出层序遍历的结果。
 *
 * 输入描述
 * 每个输入文件一行，第一个字符串表示后序遍历结果，第二个字符串表示中序遍历结果。（每串只包含大写字母）
 *
 * 中间用单空格分隔。
 *
 * 输出描述
 * 输出仅一行，表示层序遍历的结果，结尾换行。
 */
public class GenetateTree1 {

    public static void main(String[] args) {
        String str = "ASDFG";
        System.out.println(str.substring(str.indexOf("D")));
        System.out.println(str.substring(2,4));
        System.out.println("-----------");
        Scanner scanner = new Scanner(System.in);
        String[] split = scanner.nextLine().split(" ");
        scanner.close();

        String postOrder = split[0];
        String inOrder = split[1];

        Node root = generateNode(postOrder, inOrder);
        bfs(root);
    }

    private static Node generateNode(String postOrder, String inOrder) {
        if (postOrder.isEmpty() || inOrder.isEmpty()) return null;
        char last = postOrder.charAt(postOrder.length() - 1);
        Node node = new Node(last);
        int index = inOrder.indexOf(last);
        String leftSIn = inOrder.substring(0, index);
        String rightIn = inOrder.substring(index+1);
        String leftPost = postOrder.substring(0, leftSIn.length());
        String rightPost = postOrder.substring(leftSIn.length(), postOrder.length()-1);

        Node left = generateNode(leftPost, leftSIn);
        Node right = generateNode(rightPost, rightIn);
        node.left = left;
        node.right = right;
        return node;
    }

    private static void bfs(Node node) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            Node poll = queue.poll();
            System.out.print(poll.value);
            if (poll.left!=null) queue.add(poll.left);
            if (poll.right!=null) queue.add(poll.right);
        }
    }

    static class Node {
        Node left, right;
        char value;
        Node(char value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }
}


